package com.example.hot100;

/**
 * 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
 *  设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
 *  你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
 *
 *  示例:
 *  输入: [1,2,3,0,2]
 * 输出: 3
 * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 */
public class Leetcode309_MaxProfit {

    public static void main(String[] args) {
        int[] prices = {1, 2, 3, 0, 2};
        System.out.println(new Solution().maxProfit(prices));
    }

    static class Solution {

        /**
         * 动态规划(空间优化)
         * @param prices
         * @return
         */
        private int maxProfit2(int[] prices) {
            int dpHave = -prices[0];
            int dpCold = 0;
            int dpNo = 0;
            for (int i = 1; i < prices.length; i++) {
                int tmpDpHave = Math.max(dpHave, dpNo - prices[i]);
                int tmpDpCold = dpHave + prices[i];
                int tmpDpNo = Math.max(dpCold, dpNo);
                dpHave = tmpDpHave;
                dpCold = tmpDpCold;
                dpNo = tmpDpNo;
            }
            return Math.max(dpNo, dpCold);
        }

        /**
         * 动态规划
         * @param prices
         * @return
         */
        private int maxProfit1(int[] prices) {
            int[] dpHave = new int[prices.length]; // dpHave[i]表示第i天手里有股票的能获得的最大收益
            int[] dpCold = new int[prices.length]; // dpCold[i]表示第i天手里没有股票且处于冷冻期(即恰在第i天时卖出股票)能获得的最大收益
            int[] dpNo = new int[prices.length]; // dpNo[i]表示第i天手里没有股票且不处于冷冻期(即在第i天前已经卖出股票)能获得的最大收益
            dpHave[0] = -prices[0];
            dpCold[0] = 0;
            dpNo[0] = 0;

            for (int i = 1; i < prices.length; i++) {
                dpHave[i] = Math.max(dpHave[i - 1], dpNo[i - 1] - prices[i]);
                dpCold[i] = dpHave[i - 1] + prices[i];// 恰好在第i天卖出
                dpNo[i] = Math.max(dpNo[i - 1], dpCold[i - 1]);
            }

            return Math.max(dpNo[prices.length - 1], dpCold[prices.length - 1]);
        }

        public int maxProfit(int[] prices) {
            return maxProfit2(prices);
        }
    }
}
